//+------------------------------------------------------------------+
//|                                                    SortedMap.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic/Interfaces/IMap.h>              // 继承映射接口 IMap<TKey, TValue>，获取基础键值对能力
#include <Generic/Interfaces/IComparer.h>          // 比较器接口，支持自定义键的排序规则
#include <Generic/Internal/DefaultComparer.h>      // 默认比较器，适配基础类型（int/string等）的排序
#include <Generic/Internal/CompareFunction.h>      // 内部比较工具函数，支撑比较器实现
#include "HashMap.h"                               // 哈希映射类（依赖其 CKeyValuePair 键值对结构）
#include "SortedSet.h"                             // 有序集合类（与有序映射共享排序逻辑）

//+------------------------------------------------------------------+
//| CSortedMap<TKey, TValue> 类：有序键值对映射实现类                 |
//| 核心定位：实现 IMap<TKey, TValue> 接口，基于红黑树（CRedBlackTree）作为底层存储， |
//|           按“键”的排序规则维护键值对，支持高效的有序访问与操作       |
//| 核心特性：                                                      |
//|  1. 键有序性：所有键值对按“键”的排序规则（由比较器定义）有序存储；    |
//|  2. 键唯一性：同一键仅对应一个值，重复添加相同键会失败；            |
//|  3. 高效操作：插入/删除/查找/范围查询均为 O(log n) 时间复杂度（依赖红黑树）； |
//|  4. 灵活排序：支持默认排序（升序）或自定义比较器（如降序、按字段排序）； |
//|  5. 有序输出：遍历/复制时按键的排序规则输出，无需额外排序步骤；        |
//| 适用场景：所有需要“按键有序管理键值对”且需高效增删查的场景，典型如：  |
//|  - 有序配置项（按配置名称/优先级排序的参数列表，如 EA 策略参数）；     |
//|  - 排序统计数据（按时间/数值排序的统计结果，如按订单金额排序的订单列表）； |
//|  - 范围查询场景（如查询价格在 [100, 200] 之间的品种-价格映射）；     |
//|  - 有序缓存（按过期时间排序的缓存数据，优先清理最早过期的键值对）；     |
//+------------------------------------------------------------------+
template<typename TKey, typename TValue>
class CSortedMap : public IMap<TKey, TValue>
  {
protected:
   CRedBlackTree<CKeyValuePair<TKey, TValue>*>* m_tree;  // 底层红黑树（存储键值对，实现有序性与高效操作）
   IComparer<TKey>* m_comparer;                          // 键的比较器（定义键的排序规则，如升序/降序）
   bool              m_delete_comparer;                   // 是否自动释放比较器内存（外部传入比较器时为 false）

public:
   //----------------------------------------------------------------
   // 构造与析构接口
   //----------------------------------------------------------------
   /**
    * @brief 默认构造函数：创建空有序映射，使用默认键比较器（升序）
    * @note 默认比较器为 CDefaultComparer<TKey>，适配基础类型（int/double/string/datetime 等）的自然升序
    */
                     CSortedMap(void);

   /**
    * @brief 指定比较器构造函数：创建空有序映射，使用自定义键比较器
    * @param comparer [in] 键的比较器（实现 IComparer<TKey> 接口，定义排序规则）
    * @example 按订单ID降序排序 → 传入 OrderIdDescComparer 实例；按字符串长度排序 → 传入 StringLengthComparer 实例
    */
                     CSortedMap(IComparer<TKey>* comparer);

   /**
    * @brief 从映射构造：创建有序映射并复制指定映射的所有键值对，使用默认比较器
    * @param map [in] 源映射（实现 IMap<TKey, TValue> 接口，如 CHashMap/CSortedMap）
    * @note 复制后键值对按默认比较器规则重新排序，重复键（源映射中不应存在）仅保留一个
    */
                     CSortedMap(IMap<TKey, TValue>* map);

   /**
    * @brief 映射+比较器构造：创建有序映射并复制指定映射的所有键值对，使用自定义比较器
    * @param map [in] 源映射（实现 IMap<TKey, TValue> 接口）
    * @param comparer [in] 键的比较器（实现 IComparer<TKey> 接口）
    * @note 复制后键值对按自定义比较器规则排序
    */
                     CSortedMap(IMap<TKey, TValue>* map, IComparer<TKey>* comparer);

   /**
    * @brief 析构函数：清理有序映射资源
    * @note 1. 若比较器为内部创建（默认比较器），自动释放比较器内存；
    *       2. 递归删除红黑树中所有键值对（CKeyValuePair）的内存；
    *       3. 释放红黑树及树内节点的内存，避免内存泄漏
    */
                    ~CSortedMap(void);

   //----------------------------------------------------------------
   // 键值对添加接口
   //----------------------------------------------------------------
   /**
    * @brief 添加键值对对象到有序映射（继承自 IMap 接口）
    * @param value [in] 待添加的键值对（CKeyValuePair<TKey, TValue> 实例）
    * @return bool - 添加结果：true=添加成功（键不存在）；false=添加失败（键已存在或键值对为 NULL）
    * @note 内部调用红黑树的 Add 方法，按比较器规则插入键值对，保证有序性
    */
   bool              Add(CKeyValuePair<TKey, TValue>* value) { return m_tree->Add(value); }

   /**
    * @brief 添加指定键和值到有序映射（创建键值对后插入）
    * @param key [in] 键（唯一标识，需支持比较器的排序逻辑）
    * @param value [in] 与键关联的值
    * @return bool - 添加结果：true=添加成功（键不存在）；false=添加失败（键已存在）
    * @note 内部创建 CKeyValuePair 实例，插入红黑树后自动按键排序；添加失败时会释放创建的键值对内存
    */
   bool              Add(TKey key, TValue value);

   //----------------------------------------------------------------
   // 基础信息与包含性检查接口
   //----------------------------------------------------------------
   /**
    * @brief 获取有序映射中的键值对数量（继承自 IMap 接口）
    * @return int - 键值对数量（≥0，空映射返回0）
    */
   int               Count(void) { return m_tree->Count(); }

   /**
    * @brief 检查映射是否包含指定键值对（继承自 IMap 接口）
    * @param item [in] 待检查的键值对（CKeyValuePair<TKey, TValue> 实例）
    * @return bool - 检查结果：true=包含（键存在且值匹配）；false=不包含
    * @note 内部调用红黑树的 Contains 方法，按键查找后比对值
    */
   bool              Contains(CKeyValuePair<TKey, TValue>* item) { return m_tree->Contains(item); }

   /**
    * @brief 检查映射是否包含指定的键值组合
    * @param key [in] 待检查的键
    * @param value [in] 待检查的值
    * @return bool - 检查结果：true=包含（键存在且对应值匹配）；false=不包含
    * @note 内部逻辑：先按键查找键值对，再通过默认值比较器（CDefaultEqualityComparer）比对值
    */
   bool              Contains(TKey key, TValue value);

   /**
    * @brief 检查映射是否包含指定的键（核心高效操作）
    * @param key [in] 待检查的键
    * @return bool - 检查结果：true=键存在；false=键不存在
    * @note 内部通过红黑树按键查找，时间复杂度 O(log n)，比 ContainsValue 高效
    */
   bool              ContainsKey(TKey key);

   /**
    * @brief 检查映射是否包含指定的值
    * @param value [in] 待检查的值
    * @return bool - 检查结果：true=值存在；false=值不存在
    * @note 内部逻辑：将所有键值对复制到数组，线性遍历比对值，时间复杂度 O(n)，效率低于 ContainsKey
    */
   bool              ContainsValue(TValue value);

   /**
    * @brief 获取当前使用的键比较器
    * @return IComparer<TKey>* - 比较器实例（NULL 表示未设置）
    */
   IComparer<TKey>*  Comparer(void) const { return(m_comparer); }

   //----------------------------------------------------------------
   // 批量复制接口
   //----------------------------------------------------------------
   /**
    * @brief 将映射中的所有键值对按“键的排序规则”复制到键值对数组（继承自 IMap 接口）
    * @param dst_array [out] 目标键值对数组（需提前分配空间，或由方法自动扩容）
    * @param dst_start [in] 目标数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的键值对数量（等于 Count()）
    * @note 复制的是键值对的克隆体（Clone()），修改目标数组元素不影响原映射
    */
   int               CopyTo(CKeyValuePair<TKey, TValue>*& dst_array[], const int dst_start=0);

   /**
    * @brief 将映射中的键和值分别复制到两个独立数组（按键的排序规则）
    * @param dst_keys [out] 目标键数组（存储所有键，按排序规则排列）
    * @param dst_values [out] 目标值数组（存储所有值，与键数组按索引对应）
    * @param dst_start [in] 数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的键值对数量（等于 Count()）
    * @note 键数组与值数组的索引严格对应（dst_keys[i] 对应 dst_values[i]）
    */
   int               CopyTo(TKey &dst_keys[], TValue &dst_values[], const int dst_start=0);

   //----------------------------------------------------------------
   // 清理与删除接口
   //----------------------------------------------------------------
   /**
    * @brief 清空映射中的所有键值对（继承自 IMap 接口）
    * @note 1. 递归删除红黑树中所有键值对（CKeyValuePair）的内存；
    *       2. 清空红黑树，重置映射状态（Count() 变为0）；
    *       3. 保留比较器，后续可继续添加键值对
    */
   void              Clear(void);

   /**
    * @brief 从映射中删除指定键值对（继承自 IMap 接口）
    * @param item [in] 待删除的键值对（CKeyValuePair<TKey, TValue> 实例）
    * @return bool - 删除结果：true=删除成功（键值对存在）；false=删除失败
    * @note 内部调用红黑树的 Remove 方法，删除后自动维护树的有序性与平衡性
    */
   bool              Remove(CKeyValuePair<TKey, TValue>* item) { return m_tree->Remove(item); }

   /**
    * @brief 从映射中删除指定键对应的键值对
    * @param key [in] 待删除的键
    * @return bool - 删除结果：true=删除成功（键存在）；false=删除失败（键不存在）
    * @note 内部逻辑：先按键查找对应的键值对节点，删除节点后释放键值对内存，红黑树自动平衡
    */
   bool              Remove(TKey key);

   //----------------------------------------------------------------
   // 键值访问接口
   //----------------------------------------------------------------
   /**
    * @brief 通过键安全获取对应的值（继承自 IMap 接口，核心高效操作）
    * @param key [in] 用于查找的键
    * @param value [out] 输出参数，接收找到的值（仅当返回 true 时有意义）
    * @return bool - 获取结果：true=键存在，成功获取值；false=键不存在
    * @note 内部通过红黑树按键查找，时间复杂度 O(log n)
    */
   bool              TryGetValue(TKey key, TValue &value);

   /**
    * @brief 通过键安全修改对应的值（继承自 IMap 接口）
    * @param key [in] 用于定位的键
    * @param value [in] 待设置的新值
    * @return bool - 修改结果：true=键存在，成功修改值；false=键不存在，修改失败
    * @note 仅修改值，不改变键的位置（键的排序规则不变）
    */
   bool              TrySetValue(TKey key, TValue value);

private:
   //----------------------------------------------------------------
   // 内部辅助接口（不对外暴露）
   //----------------------------------------------------------------
   /**
    * @brief 静态辅助方法：递归遍历红黑树所有节点，删除节点中存储的键值对（CKeyValuePair）内存
    * @param node [in] 当前遍历的红黑树节点（CRedBlackTreeNode 实例）
    * @note 采用“后序遍历”策略：先删除右子树节点 → 再删除当前节点键值对 → 最后删除左子树节点，确保所有键值对都被释放
    */
   static void       ClearNodes(CRedBlackTreeNode<CKeyValuePair<TKey, TValue>*>* node);
  };
//+------------------------------------------------------------------+